Graphe connexe et composantes connexes

 Définition Graphe connexe, composantes connexes d’un graphe

• Un graphe est dit connexe si deux sommets quelconques sont reliés par une chaîne (c’est un graphe en « un seul morceau »).
  
• On appelle composante connexe du graphe  \(G\) un sous-graphe connexe maximal de  \(G\)   (c’est-à-dire qui n’est contenu dans aucun autre sous-graphe connexe).
  

Exemples

1. Ce graphe est connexe : tous les sommets peuvent être reliés deux à deux entre eux par une chaîne.

2. Ce graphe n’est pas connexe : il a deux composantes connexes :

Remarque

Dans le cas d’un graphe orienté, on parle de graphe fortement connexe si deux sommets
quelconques sont reliés par un chemin (donc il existe un chemin dans chaque sens).

Exemples

1. Ce graphe est fortement connexe : tous les sommets peuvent être reliés deux à deux entre eux par un chemin dans chaque sens.

2. Ce graphe n’est pas fortement connexe : on peut aller de n’importe quel autre sommet au
sommet \(3\) , mais il n’existe aucun moyen de partir du sommet \(3\)  pour aller vers un autre sommet.